207. Course Schedule
Medium

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.
Accepted
606,194
Submissions
1,363,880
Seen this question in a real interview before?
Show Hint 1
This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Show Hint 2
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Show Hint 3
Topological sort could also be done via BFS.

Average Rating: 4.17 (72 votes)

Premium

Solution


Approach 1: Backtracking

Intuition

The problem could be modeled as yet another graph traversal problem, where each course can be represented as a vertex in a graph and the dependency between the courses can be modeled as a directed edge between two vertex.

And the problem to determine if one could build a valid schedule of courses that satisfies all the dependencies (i.e. constraints) would be equivalent to determine if the corresponding graph is a DAG (Directed Acyclic Graph), i.e. there is no cycle existed in the graph.

pic

A typical strategy for graph traversal problems would be backtracking or simply DFS (depth-first search).

Here let us start with the backtracking algorithm, which arguably might be more intuitive.

As a reminder, backtracking is a general algorithm that is often applied to solve the constraint satisfaction problems, which incrementally builds candidates to the solutions, and abandons a candidate (i.e. backtracks) as soon as it determines that the candidate would not lead to a valid solution.

The general idea here is that we could enumerate each course (vertex), to check if it could form cyclic dependencies (i.e. a cyclic path) starting from this course.

The check of cyclic dependencies for each course could be done via backtracking, where we incrementally follow the dependencies until either there is no more dependency or we come across a previously visited course along the path.

Algorithm

The overall structure of the algorithm is simple, which consists of three main steps:

  • Step 1). we build a graph data structure from the given list of course dependencies. Here we adopt the adjacency list data structure as shown below to represent the graph, which can be implemented via hashmap or dictionary. Each entry in the adjacency list represents a node which consists of a node index and a list of neighbors nodes that follow from the node. pic
  • Step 2). we then enumerate each node (course) in the constructed graph, to check if we could form a dependency cycle starting from the node.
  • Step 3). we perform the cyclic check via backtracking, where we breadcrumb our path (i.e. mark the nodes we visited) to detect if we come across a previously visited node (hence a cycle detected). We also remove the breadcrumbs for each iteration.
Current
1 / 5

Complexity

  • Time Complexity: O(E+V2)\mathcal{O}(|E| + |V| ^ 2) where E|E| is the number of dependencies, V|V| is the number of courses and dd is the maximum length of acyclic paths in the graph.

    • First of all, it would take us E|E| steps to build a graph in the first step.
    • For a single round of backtracking, in the worst case where all the nodes chained up in a line, it would take us maximum V|V| steps to terminate the backtracking. pic
    • Again, follow the above worst scenario where all nodes are chained up in a line, it would take us in total i=1Vi=(1+V)V2\sum_{i=1}^{|V|}{i} = \frac{(1+|V|)\cdot|V|}{2} steps to finish the check for all nodes.
    • As a result, the overall time complexity of the algorithm would be O(E+V2)\mathcal{O}(|E| + |V| ^ 2).

  • Space Complexity: O(E+V)\mathcal{O}(|E| + |V|), with the same denotation as in the above time complexity.

    • We built a graph data structure in the algorithm, which would consume E+V|E| + |V| space.
    • In addition, during the backtracking process, we employed a sort of bitmap (path) to keep track of all visited nodes, which consumes V|V| space.
    • Finally, since we implement the function in recursion, which would incur additional memory consumption on call stack. In the worst case where all nodes are chained up in a line, the recursion would pile up V|V| times.
    • Hence the overall space complexity of the algorithm would be O(E+3V)=O(E+V)\mathcal{O}(|E| + 3\cdot|V|) = \mathcal{O}(|E| + |V|) .


Intuition

As one might notice that, with the above backtracking algorithm, we would visit certain nodes multiple times, which is not the most efficient way.

pic

For instance, in the above graph where the nodes are chained up in a line, the backtracking algorithm would end up of being a nested two-level iteration over the nodes, which we could rewrite as the following pseudo code:

for i in range(0, len(nodes)):
    # start from the current node to check if a cycle might be formed.
    for j in range(i, len(nodes)):
        isCyclic(nodes[j], courseDict, path)

One might wonder that if there is a better algorithm that visits each node once and only once. And the answer is yes.

In the above example, for the first node in the chain, once we've done the check that there would be no cycle formed starting from this node, we don't have to do the same check for all the nodes in the downstream.

The rationale is that given a node, if the subgraph formed by all descendant nodes from this node has no cycle, then adding this node to the subgraph would not form a cycle either.

From the perspective of graph traversal, the above rationale could be implemented with the strategy of postorder DFS (depth-first search), in which strategy we visit a node's descendant nodes before the node itself.

Algorithm

We could implement the postorder DFS based on the above backtracking algorithm, by simply adding another bitmap (i.e. checked[node_index]) which indicates whether we have done the cyclic check starting from a particular node.

Here are the breakdowns of the algorithm, where the first 2 steps are the same as in the previous backtracking algorithm.

  • Step 1). We build a graph data structure from the given list of course dependencies.
  • Step 2). We then enumerate each node (course) in the constructed graph, to check if we could form a dependency cycle starting from the node.
  • Step 3.1). We check if the current node has been checked before, otherwise we enumerate through its child nodes via backtracking, where we breadcrumb our path (i.e. mark the nodes we visited) to detect if we come across a previously visited node (hence a cycle detected). We also remove the breadcrumbs for each iteration.
  • Step 3.2). Once we visited all the child nodes (i.e. postorder), we mark the current node as checked.

Note, one could also use a single bitmap with 3 states such as not_visited, visited, checked, rather than having two bitmaps as we did in the algorithm, though we argue that it might be clearer to have two separated bitmaps.

Complexity

  • Time Complexity: O(E+V)\mathcal{O}(|E| + |V|) where V|V| is the number of courses, and E|E| is the number of dependencies.

    • As in the previous algorithm, it would take us E|E| time complexity to build a graph in the first step.
    • Since we perform a postorder DFS traversal in the graph, we visit each vertex and each edge once and only once in the worst case, i.e. E+V|E| + |V|.

  • Space Complexity: O(E+V)\mathcal{O}(|E| + |V|), with the same denotation as in the above time complexity.

    • We built a graph data structure in the algorithm, which would consume E+V|E| + |V| space.
    • In addition, during the backtracking process, we employed two bitmaps (path and visited) to keep track of the visited path and the status of check respectively, which consumes 2V2 \cdot |V| space.
    • Finally, since we implement the function in recursion, which would incur additional memory consumption on call stack. In the worst case where all nodes chained up in a line, the recursion would pile up V|V| times.
    • Hence the overall space complexity of the algorithm would be O(E+4V)=O(E+V)\mathcal{O}(|E| + 4\cdot|V|) = \mathcal{O}(|E| + |V|).


Approach 3: Topological Sort

Intuition

Actually, the problem is also known as topological sort problem, which is to find a global order for all nodes in a DAG (Directed Acyclic Graph) with regarding to their dependencies.

A linear algorithm was first proposed by Arthur Kahn in 1962, in his paper of "Topological order of large networks". The algorithm returns a topological order if there is any. Here we quote the pseudo code of the Kahn's algorithm from wikipedia as follows:

L = Empty list that will contain the sorted elements
S = Set of all nodes with no incoming edge

while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

To better understand the above algorithm, we summarize a few points here:

  • In order to find a global order, we can start from those nodes which do not have any prerequisites (i.e. indegree of node is zero), we then incrementally add new nodes to the global order, following the dependencies (edges).
  • Once we follow an edge, we then remove it from the graph.
  • With the removal of edges, there would more nodes appearing without any prerequisite dependency, in addition to the initial list in the first step.
  • The algorithm would terminate when we can no longer remove edges from the graph. There are two possible outcomes:
    • 1). If there are still some edges left in the graph, then these edges must have formed certain cycles, which is similar to the deadlock situation. It is due to these cyclic dependencies that we cannot remove them during the above processes.
    • 2). Otherwise, i.e. we have removed all the edges from the graph, and we got ourselves a topological order of the graph.

Algorithm

Following the above intuition and pseudo code, here we list some sample implementations.

Current
1 / 7

Note that we could use different types of containers, such as Queue, Stack or Set, to keep track of the nodes that have no incoming dependency, i.e. indegree = 0. Depending on the type of container, the resulting topological order would be different, though they are all valid.

Complexity

  • Time Complexity: O(E+V)\mathcal{O}(|E| + |V|) where V|V| is the number of courses, and E|E| is the number of dependencies.

    • As in the previous algorithm, it would take us E|E| time complexity to build a graph in the first step.
    • Similar with the above postorder DFS traversal, we would visit each vertex and each edge once and only once in the worst case, i.e. E+V|E| + |V|.
    • As a result, the overall time complexity of the algorithm would be O(2E+V)=O(E+V)\mathcal{O}(2\cdot|E| + |V|) = \mathcal{O}(|E| + |V|).

  • Space Complexity: O(E+V)\mathcal{O}(|E| + |V|), with the same denotation as in the above time complexity.

    • We built a graph data structure in the algorithm, which would consume E+V|E| + |V| space.
    • In addition, we use a container to keep track of the courses that have no prerequisite, and the size of the container would be bounded by V|V|.
    • As a result, the overall space complexity of the algorithm would be O(E+2V)=O(E+V)\mathcal{O}(|E| + 2\cdot|V|) = \mathcal{O}(|E| + |V|).

Report Article Issue

Comments: 70
clock330's avatar
Read More

I feel stressed when I realize the fact that I have to take up to 10^5 courses

223
Show 1 reply
Reply
Share
Report
ufdeveloper's avatar
Read More

This is a hard problem

207
Show 6 replies
Reply
Share
Report
OmQfda2N9AdvUNbCE37mZKlARMo's avatar
Read More

Am I tripping or the illustration in Approach 3 is ... WRONG? After 3 and 4 are done, 0 still has indegree of 1 from node 1 ... How could there be a toposort here?

19
Show 3 replies
Reply
Share
Report
chu_steven's avatar
Read More

Can you provide a visual example of Approach (3) for a graph that does have a cycle? That'd be helpful :)

17
Show 1 reply
Reply
Share
Report
kushalmahajan's avatar
Read More

For topological sort the solution given in Approach 2 of https://leetcode.com/problems/course-schedule-ii/solution/ is better than the premium solution here. Maybe the article with an update to that approach and animation will make it a one stop to build intuition.

9
Show 1 reply
Reply
Share
Report
Algorithm0110's avatar
Read More

Approach 1 time complexity seems incorrect. DFS cycle check should be O(V+E), which invalidates the analysis.

7
Show 3 replies
Reply
Share
Report
nostradamus29's avatar
Read More

Hey coders.. when I was first solving this problem, I build a hashmap like this -
For prerequisites = [[1,0], [1,2], [2,3]], my hashmap is -
1 -> 0,2
2 -> 3
So, I go through dependencies of 1 which are 0,2.
0 has no dependency
2 has 3 and finally 3 has no dependency
So everything is ok

After looking at the solution, I saw they built the hashmap like this -
0 -> 1
2 -> 1
3 -> 2

This feels kinda inverted.
Can someone please explain me what I am missing ?

6
Show 3 replies
Reply
Share
Report
iamsdhar's avatar
Read More

The solution posted by Leetcode is cancer to my eyes. This problem can easily be solved by Kahn's Algorithm (Topological Sorting). Here is my solution which isn't as complex as the one posted above.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        HashMap<Integer, Boolean> seen = new HashMap<>();
        int[] indegree = new int[numCourses];
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        
        // Building the graph
        for(int[] courses : prerequisites) {
            int to = courses[0];
            int from = courses[1];
            var list = map.getOrDefault(from, new ArrayList<>());
            list.add(to);
            map.put(from, list);
            indegree[to]++;
        }
        
        // Implementation of Kahn's Alg
        for(int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) q.add(i);
        }
        while(!q.isEmpty()) {
            int node = q.peek();
            q.poll();
            count++;
            if(map.containsKey(node)) {
                for(int nei : map.get(node)) {
                    indegree[nei]--;
                    if(indegree[nei] == 0) {
                        q.add(nei);
                    }
                }
            }
        }
        return count == numCourses;
    }
}

14
Show 2 replies
Reply
Share
Report
sharabiania's avatar
Read More

is it possible to solve this using BFS?

4
Show 1 reply
Reply
Share
Report
monester's avatar
Read More

tbh approach 1 is the only answer I can come up with in an interview. xD

5
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/03/2021 19:51Accepted52 ms14 MBcpp
04/24/2021 08:25Accepted24 ms14 MBcpp
08/25/2020 16:34Accepted56 ms13.8 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.